Summary and Contributions: The paper deals with a variant of the dueling or battling bandit problem, where it is allowed to pull up to k many arms in each time step. In addition, a more general class of multiwise comparison models is considered as the ones investigated in the battling bandit problem or the previously used Multinomial Logit model of related settings. A lower bound on the expected regret is shown for the general class of multiwise comparison models, which in particular gives a more refined bound as the previously shown for the case of MNL models. Moreover, one learning algorithm is suggested for the considered problem and analyzed theoretically with respect to its expected regret bound. Finally, the proposed algorithm is investigated in numerous experiments on synthetic as well as real-world datasets and compared to related algorithms. Post Rebuttal After reading the other reviews as well as the author's response, I think that the authors have not addressed two of the concerns mentioned in the reviews thoroughly enough, namely the independence of k for the complexity terms as well as the suggestion to compare with the lower bounds coming from the structured bandits.

There has been much interest in recent years in the problem of dueling bandits, where on each round the learner plays a pair of arms and receives as feedback the outcome of a relative pairwise comparison between them. Here we study a natural generalization, that we term \emph{choice bandits}, where the learner plays a set of up to k \geq 2 arms and receives limited relative feedback in the form of a single multiway choice among the pulled arms, drawn from an underlying multiway choice model. We study choice bandits under a very general class of choice models that is characterized by the existence of a unique best' arm (which we term generalized Condorcet winner), and includes as special cases the well-studied multinomial logit (MNL) and multinomial probit (MNP) choice models, and more generally, the class of random utility models with i.i.d. We propose an algorithm for choice bandits, termed Winner Beats All (WBA), with distribution dependent O(\log T) regret bound under all these choice models. The challenge in our setting is that the decision space is \Theta(n k), which is large for even moderate k .